package com.leecode;

import java.util.Stack;

public class Leet20 {
	public static void main(String[] args) {
//		System.out.println(new Leet20().isValid("){"));
		System.out.println(new Leet20().isValid2("()"));
//		System.out.println(new Leet20().isValid("(([]){})"));
	}
	public boolean isValid(String s) {
		if(s==null || s.length()==0){
			return true;
		}

		if(s.length()%2==1){
			return false;
		}
		Stack<Character> stack = new Stack();
		for (int i = 0; i < s.length();i++){
			char current = s.charAt(i);
			if (current == '(' || current == '{' || current == '[') {
				stack.push(current);
			}
			switch (current){
				case ')':
					if (stack.size()==0 || stack.peek() != '(') {
						return false;
					}
					stack.pop();
					break;
				case '}':
					if (stack.size()==0 || stack.peek() != '{') {
						return false;
					}
					stack.pop();
					break;
				case ']':
					if (stack.size()==0 || stack.peek() != '[') {
						return false;
					}
					stack.pop();
					break;
			}
		}
		if (stack.size() == 0) {
			return true;
		}
		return false;
	}

	/**
	 * 考点1:放入123,要逆序比较321,要想到Stack
	 * 考点2:bug2
	 */
	public boolean isValid2(String s) {
		if (s.length() == 0) return true;

		//123 -3-2-1先比较3,再2,再1
		Stack<Character> stack = new Stack();
		for (int a = 0; a < s.length(); a++) {
			char cha = s.charAt(a);
			if (cha == '(' || cha == '{' || cha == '[') {
				stack.push(cha);
			} else {
				if (stack.isEmpty()) {
					return false;
				} else {
					char temp = stack.pop();
					if (temp == '(' && cha == ')') continue;
					if (temp == '[' && cha == ']') continue;
					if (temp == '{' && cha == '}') continue;
					return false;
				}
			}
		}

//		return true;//bug2
		if (stack.isEmpty()) return true;
		return false;
	}
}
